When user data stored in a memory is read out of the memory, the read-out user data may be different from the original value thereof. In order to handle such a problem, there is a typical method of encoding the user data for error correction, generating redundant data called parity, and storing a set of the user data and the parity in the memory. At the time of the occurrence of errors, the correction is performed using the parity data.
As the error correcting code, there are a BCH code, an RS (Reed Solomon) code and the like, for example. In recent years, a probability of errors occurring increases as the memory becomes miniaturized and multivalued, and thus a stronger error correcting code is requested. In order to improve an error correction capability, it is a general method to increase the data size of the parity. However, there are problems in such a method such as an increase in circuit scale necessary for the error correcting code, and a decrease in capacity of the user data to be stored (or, an increase in memory size).